It is a known technology in which the pattern of input signals is recognized and the signal sequence that has been input is converted into a corresponding symbol string. For example, there are known technologies such as the technology for recognizing speech signals; the optical character recognition (OCR) technology in which characters are recognized from an image in which the characters are written; the technology for recognizing handwritten characters; and the technology for recognizing a gesture or sign language from an image. As a device for implementing such technologies, a decoder is known that searches a digraph which is formed by adding output symbols to a weighted finite state automaton (for example, searches a weighted finite state transducer).
A decoder for searching a digraph, such as a weighted finite state transducer, can also generate a lattice during the search. However, in such a decoder, as the search is carried on, a large number of nodes and arcs need to be added in a lattice. Moreover, in such a decoder, as the search is carried on, there is an increase in the pointers or arcs which represent the inter-node connections and which need to be appropriately destroyed. For that reason, in a decoder capable of generating a lattice during the search, the amount of processing during the search becomes enormous.